package Year22_Month05.day29;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 中序遍历_迭代写法 {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        //栈为空并且cur == null的时候就遍历完毕
        while(!stack.isEmpty() || cur != null){
            //首先就是往左走，一直往左走，走到没有地方走为止
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{//如果说左子树为null的时候，就把当前节点值加入，然后遍历右子树的左子树
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
}
